Questions to consider

• How do pipes differ from FIFOs and when would you use each?
• What considerations matter when choosing between pipes, FIFOs, and memory-mapped files?

IPC taxonomy

Pipes (anonymous pipes)

• Pipes are unidirectional; one end must be designated as the reading end and the other as the writing end
• Pipes are order preserving; all data read from the receiving end of the pipe will match the order in which it was written into the pipe
• Pipes have a limited capacity and they use blocking I/O; if a pipe is full, any additional writes to the pipe will block the process until some of the data has been read
• Pipes send data as unstructured byte streams. There are no pre-defined characteristics to the data exchanged, such as a predictable message length

Pipes (cont’d)

• Pipes create a producer-consumer buffer between two processes
• Cannot be accessed outside of the creating process (child inherits the pipe since it’s a fd)
• The operating system manages a queue for each pipe to accommodate different input and output rates
• Facilitates the canonical chaining together of small UNIX utilities to do more sophisticated processing

Pipe bugs

int pipefd[2];
pipe (pipefd);

if (fork () == 0)
  exit (0);

char buffer[10];
read (pipefd[0], buffer, sizeof (buffer));

• What will happen here?
  • Parent will block until an EOF is written into the pipe. Since the child is the only other process that could write to the pipe and the child exits without writing anything, and the parent has not closed its write end, the parent will block indefinitely.

Named pipes (also known as FIFOs)

• Of course there is another type that don’t share the same characteristics
• Named pipes are bidirectional, don’t have the parent-child relationship
  • Creates a persistent file-like name
  • Require a reader and writer

Named pipes (cont’d)

• Really a data stream (ordering, buffering, reliability, authentication all implied)
• They are not regular files, though they look like them
  • Once data has been read from a FIFO, the data is discarded and cannot be read again
  • Cannot broadcast: only one read()
  • Not wise to use bidirectionally, why?

Shared memory with mmap

• Provide extremely fast IPC data exchange. i.e., when one process writes to the region, that data is immediately accessible by the other process without having to invoke a system call
• Unlike pipes, memory-mapped files create persistent IPC. Once the data is written to the shared region, it can be repeatedly accessed by other processes

Memory mapped files: POSIX and System V

• These two ultimately mmap a file, but do some trickery beforehand and use special files
• POSIX == named, RAM-backed file descriptors
  • name → fd → mmap
  • Object survives until the last reference is gone
  • usually backed by tmpfs (/dev/shm)
• System V shared memory
  • Predates POSIX - designed before file descriptors were a universal abstraction
  • Kernel-persistent objects, you must clean up manually
    • Process exits ≠ memory freed

POSIX vs. System V

• POSIX is great, right!?
  • POSIX (e.g., shm_open()) IPC may not work in your favor in macOS
  • Some questionable engineer (obviously not a CP grad) decided to provide the header files for certain things, but they are empty stubs
    • It will compile, but could be bad
• System V is “fine”
  • shmget(): allocate
  • shmat(): attach
  • shmdt(): detach
  • shmctl(): control (destroy with IPC_RMID)

Message passing vs. shared memory

Questions to consider

• What are the differences / tradeoffs between preemptive and non-preemptive scheduling algorithms?
• What are the metrics we can attempt to optimize scheduling for a given scenario?

Preemptive vs. non-preemptive scheduling

• Non-Preemptive: The scheduler only makes scheduling decisions when a process voluntarily gives up the CPU (e.g., by blocking on I/O, completing, or explicitly yielding).
• Preemptive: The scheduler can interrupt a running process and move it to the ready queue at any time (based on time slices, priority changes, etc.), even while it’s actively executing.
• Non-preemptive is easier to implement, but
  • … doesn’t support multiprogramming very well
• Preemptive can be complicated: correctness, utilization, flexibility
  • Say a process P is preempted while in the middle of inserting an element in a data structure that another process (which is chosen by the scheduler) is going to process

Scheduling metrics

• CPU utilization: keep the CPU as busy as possible
• Throughput: # of processes that complete their execution per time unit
• Turnaround time: amount of time to execute a particular process
• Waiting time: amount of time a process has been waiting in the ready queue
• Response time: amount of time it takes from when a request was submitted until the first response is produced.

Scheduling scenarios

Which metric would you optimize for these situations?

What does the OS scheduler know about a process?

• Process characteristics that we’d like to know in order to achieve our goals
  • Processing Time (Burst Time)
  • I/O Requirements
  • Priority
  • Age
  • Dependencies
• The scheduler knows very little of the above
• In many cases we are hoping to predict the future. Easy, right?

Questions to consider

• How do FCFS, SJF, and SRTF compare in terms of tradeoffs between waiting time and response time?
• Why does SJF require predicting future CPU bursts, and how can we estimate them?
• What is starvation in the context of scheduling, and how can we prevent it?

Batch scheduling: FCFS

FCFS example

Process Burst Time  
  P1         24
  P2          3
  P3          3 

Okay, FCFS can be bad

Can we think of a better algorithm to deal with the reality that jobs run for different amounts of time?

Batch scheduling: shortest job first (SJF)

SJF: how can we predict the future?

• We can’t trust a process to tell the truth
• We can only estimate, how?
  • The past (with the hope that the process will act like it has before)
• Exponential weighted moving average: \[ EWMA_t = \alpha \times x_t + (1 - \alpha) \times EWMA_{t-1} \]
• \(\alpha = 0\)? New measurement does not get taken into account
• \(\alpha = 1\)? History does not get taken into account
• \(\alpha\) is often set to .5

SJF example

    Process Burst Time  
      P1          6
      P2          8
      P3          7
      P4          3

Do you see any problems with SJF?

• What do we do if a short process arrives after SJF has started a long running process?
• What should we do?
  • Preempt

Shortest remaining time first (SRTF)

SRTF example

    Process      Arrival Time   Burst Time
     P1               0             8
     P2               1             4
     P3               2             9
     P4               3             5

• Average waiting time = \([(0+9)+(0)+(15)+(2)]/4 = 26/4 = 6.5\)

Do you see any problems with SRTF?

• Computers aren’t static. What if short jobs continuously arrive?
  • Large jobs can starve
  • Urban legend about IBM 7074 at MIT: when shut down in 1973, low-priority processes were found which had been submitted in 1967 and had not yet been run…

Priority scheduling

• “Shortest” algos are examples of priority scheduling
• I.e., scheduling is based on some metric of priority
• Downsides
  • If not implemented carefully, indefinite blocking / starvation
  • How do we prevent starvation?
    • Aging: gradually increase the priority of processes that wait in the system for a long time

Questions to consider

• What are the key differences between batch and interactive scheduling algorithms?
• How does Round Robin improve response time compared to SJF, and what tradeoff does it introduce?
• Why might a system benefit from using multiple scheduling queues rather than a single algorithm?

Batch vs. interactive scheduling

What about response time?

Interactive algorithm: Round Robin (RR)

• FCFS with preemption
• Based on a time quantum (time slice)
  • Typically 10-100 milliseconds
  • How do we pick a quantum?
    • Very short: a lot of context switching (need a large quantum, otherwise overhead is too much to be worth it)
    • Very long -> becomes FCFS: long wait times, long turnaround times
  • Circular queue
    • New processes are added to the tail
    • If a process doesn’t complete during its quantum, context switch and added to the tail

RR example

Process Burst Time
  P1        24
  P2        3
  P3        3   

  Quantum = 4

Gaming RR

• How could a programmer “cheat” RR?
  • Spin up many processes (split tasks up and fork children)
  • Job A: 9 processes
  • Job B: 1 process
  • A gets 90% of the CPU in RR
• This actually happens in many systems that aim for rudimentary fairness

FCFS, SJF, SRTF, RR

• All have downsides

• Those that optimize turnaround / wait, can harm response time

• Those that optimize response time, can harm turnaround, wait

• What should we do?

Interactive algorithms: Multi-Level Queue (MLQ)

• We have classes of process, with different needs. Why not multiple schedulers satisfying those needs?
• Multilevel queue scheduler defined by the following parameters:
  • # of queues
  • Scheduling algorithms for each queue
  • Method used to determine which queue a process will enter when that process needs service
  • Scheduling among the queues

MLQ

Interactive algorithms: Multi-Level Feedback Queue (MLFQ)

• A process can move between the various queues
• Metrics for movement:
  • Process requirements (we serve fast processes quickly)
  • Over consumption
  • Change in priority
  • Age

MLFQ rules

• Rule 1: If Priority(A) > Priority(B), A runs (B doesn’t)

• Rule 2: If Priority(A)=Priority(B), A & B run in RR

• Rule 3: When a job enters the system, it is placed at the highest priority (the topmost queue)

• Rule 4a: If a job uses up its allotment while running, its priority is reduced (i.e., it moves down one queue)

• Rule 4b: If a job gives up the CPU (for example, by performing an I/O operation) before the allotment is up, it stays at the same priority level (i.e., its allotment is reset)

• Any problems with these???

MLFQ example: one process

MLFQ example: two processes

MLFQ example: two processes

MLFQ example: two processes

MLFQ: solving gaming

MLFQ: solving starvation

What scheduler should we use?

• Ticket booking system
  • FCFS: fairness
• Print server
  • SJF could make sense
• Web server
  • RR: fairness
• Streaming service
  • SRTF: need to quickly respond to something going wrong e.g., buffering
• General operating systems
  • MLFQ: need to handle a mix